//
// Created by DengLibin on 2018/12/16 0016.
//

/**
 *约瑟夫问题
 */

#include <iostream>
using namespace std;
#define SIZE 41  //链表长度 （总节点个数）


class PersonNode //节点
{
private:
    int num; //当前节点的编号
    bool isDead;//是否在已死（出圈表示已死）
    PersonNode * pNextNode;//下一个节点
public:
    void setNum(int num)
    {
        this->num = num;
    }
    void setIsDead(bool isDead)
    {
        this->isDead = isDead;
    }
    void setNextNode(PersonNode * nextNode)
    {
        this->pNextNode = nextNode;
    }

    int getNum()
    {
        return this->num;
    }
    bool getIsDead()
    {
        return this->isDead;
    }

    PersonNode * getNextNode()
    {
        return this->pNextNode;
    }
};
class LinkedList //链表
{
private:
    int size;//链表大小
    PersonNode *headNode;//头节点
public:
    void setSize(int size)
    {
        this->size = size;
    }

    void setHeadNode(PersonNode * headNode)
    {
        this->headNode = headNode;
    }

    PersonNode * getHeadNode()
    {
        return this->headNode;
    }

    //遍历所有的节点
    void showList()
    {
        PersonNode *tempNode = headNode;
        for (int i = 0; i < this->size; i++)
        {
            cout << tempNode->getNum() << endl;
            tempNode = tempNode->getNextNode();
        }
    }
    //显示存活的节点
    void showNoDead()
    {
        PersonNode *tempNode = headNode;
        for (int i = 0; i < this->size; i++)
        {
            if (!tempNode->getIsDead())
            {
                cout << tempNode->getNum() << endl;
            }

            tempNode = tempNode->getNextNode();
        }
    }

    //销毁
    void destroy()
    {
        PersonNode *tempNode = headNode;
        for (int i = 0; i < this->size; i++)
        {
            PersonNode *nextNode = tempNode->getNextNode();
            delete tempNode;
            tempNode = nextNode;
        }
    }
};

//初始化 SIZE个节点编号1到SIZE,最后一个节点的下一个节点指向第一个节点,返回链表
LinkedList *  init()
{
    PersonNode * headNode = new PersonNode();
    headNode->setIsDead(false);
    headNode->setNum(1); //头节点

    PersonNode* tempNode = headNode; //中间变量
    for (int i = SIZE; i >=2; i--)
    {
        PersonNode* node = new PersonNode;
        node->setIsDead(false);
        node->setNum(i);
        node->setNextNode(tempNode);
        tempNode = node;
        if (i == 2)
        {
            headNode->setNextNode(node); //头节点指向第二个节点
        }
    }
    LinkedList * list = new LinkedList();
    list->setHeadNode(headNode);
    list->setSize(SIZE);
    return list;
}

void yusefr_test1()
{
    LinkedList * list = init();
    list->showList();
    list->destroy();
    delete list;
}
//约瑟夫
void yusefr_test2(int maxNum)
{
    int i = SIZE;//存活的节点数 初始值为链表总长度
    LinkedList * list = init();
    PersonNode *tempNode = list->getHeadNode(); //游标 最开始指向头节点
    int num = 1; //数数 从1开始
    while (true)
    {

        tempNode = tempNode->getNextNode(); //游标移动
        if (!tempNode->getIsDead()) //跳过死的
        {
            num++;//num +1
        }
        if (num == maxNum)
        {
            tempNode->setIsDead(true);//数到3，该节点死了
            cout << tempNode->getNum() << "->死了" << endl;
            i--;//存活的节点减1
            num = 0;//归0
        }

        if (i < maxNum)//存活的最后的节点
        {
            break;
        }
    }

    list->showNoDead();//显示最后存活的节点
    list->destroy();
    delete list;
}

int main36(int argc, char * argv[])
{
    //yusefr_test1();
    yusefr_test2(3);
    return 0;
}